package LeetCode.month03.day78;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 16778
 * @date 2025/10/18 10:16
 * @description
 */
public class No207 {
    List<List<Integer>> edges;
    boolean valid;
    int[] visited;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        visited = new int[numCourses];
        valid = true;
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[0]).add(prerequisite[1]);
        }
        for (int i = 0; i < numCourses && valid; i++) {
            if(visited[i]==0){
                dfs(i);
            }
        }
        return valid;
    }

    private void dfs(int i) {
        visited[i]=1;
        for (Integer integer : edges.get(i)) {
            if(visited[integer]==0){
                dfs(integer);
                if(!valid){
                    return ;
                }
            }
            if(visited[integer]==1){
                valid = false;
                return ;
            }
        }
        visited[i]=2;
    }
}
